package 动态规划.样本对应模型;

import java.util.Arrays;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/4 14:11
 */
public class leetcode72编辑距离 {

    /*
     这是 一个 很不错的 题目
     */


    // 标准的动态规划
    /*
     注意 一下 初始化 basecase 时候的 一些 细节 .
     */
    public int dp(String word1,String word2){
        int len1 = word1.length();
        int len2 = word2.length();
        int [][] dp = new int [len1 + 1][len2 + 1];
        // 初始化 basecase
        dp[len1][len2] = 0;
        for(int j = 0;j < len2;j++ ){
            dp[len1][j] = len2 - j;
        }
        for(int i = 0;i < len1;i++){
            dp[i][len2] = len1 - i;
        }
        // 填表
        for(int i = len1 - 1;i >= 0;i--) {
            for (int j = len2 - 1; j >= 0; j--) {
                int ans = 500;
                if (word1.charAt(i) == word2.charAt(j)) {
                    ans = dp[i + 1][j + 1];
                }
                ans = Math.min(ans, dp[i + 1][j + 1] + 1);
                ans = Math.min(ans, dp[i + 1][j] + 1);
                ans = Math.min(ans, dp[i][j + 1] + 1);
                dp[i][j] = ans;
            }
        }
        return dp[0][0];
    }

     // AC
    /*
    basecase 整的有点难受 ,要不然 早 AC 了
    这个 basecase 真的 是不好 思考到
    主要是没遇到过 这样的问题 的模型
     */
    // 直接 上 记忆化搜索
    public int solution(String s1,String s2){
        int [][]dp = new int [s1.length() + 1][s2.length() + 1];
        for(int i = 0;i <= s1.length();i++){
            Arrays.fill(dp[i],-1);
        }
        return recursion(0,0,s1,s2,dp);
    }
    public int recursion(int i,int j,String s1,String s2,int dp[][]){
        if(dp[i][j] != -1)
            return dp[i][j];
        if(i == s1.length() && j == s2.length()){
            return 0;
        }
        // 剩下的是不满足 条件 的 返回 一个 无法 对 结果 造成 干扰 的数值就行, 这里不能 写 Integer.Max
        // 此条件说明 j != s2.length(); 那么 说明 s1 不够长, 直接 将 与 s2 差的字符部分直接  补全
        if(i == s1.length()){
            return s2.length() - j;
        }
        // 此时 说明 s1 多出了一部分字符 ,直接删去 多的字符数量
        if(j == s2.length()){
            return s1.length() - i;
        }
        int ans = 500;
        if(s1.charAt(i) == s2.charAt(j)){
            ans = recursion(i + 1,j + 1,s1,s2,dp);
        }
        // no equals , 就 进行 三种 操作 情况, 找出最小值
        // 替换
        ans = Math.min(ans,recursion(i + 1,j + 1,s1,s2,dp) + 1);
        // 删除
        ans = Math.min(ans,recursion(i + 1,j,s1,s2,dp) + 1);
        // 插入 这里 是 指 插入在  i 字符的前面, 插在 后面,没法写
        ans = Math.min(ans,recursion(i, j + 1,s1,s2,dp) + 1);
        return dp[i][j] = ans;
    }


}
